package random_test;


public class Test {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        reverseKGroup(node1,2);
        System.out.println("=======");
    }


    static public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || k == 1) return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode newhead = new ListNode(-1);
        ListNode tail = newhead;
        while(fast != null) {
            //1. 先让 fast 走K - 1步, 检查是否需要翻转
            int i = k - 1;
            for(; fast != null &&  i > 0; i--) {
                fast = fast.next;
            }
            //2. 如果 i > 0 ，剩下的结点不翻转；否则从slow 到 fast 进行头插法
            if(i == 0 && fast != null) {
                //让第一次 未开始翻转的 fast结点成为头结点
                if(newhead == tail) {
                    newhead.next = fast;
                }
                ListNode tmpHead = null;
                while(slow != fast.next) {
                    ListNode slowNext = slow.next;
                    slow.next = tmpHead;
                    tmpHead = slow;
                    slow = slowNext;
                }
                tail.next = tmpHead;
                tail = fast;
                fast = fast.next;
            }else {
                tail.next = slow;
            }
        }


        return newhead.next;
    }
}
